#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define N 20
#define MAX 10000

int main(void)
{
	srand(time(NULL));

	int arr[N];
	int i, j, t, pos;
	int min = MAX;
	int max = 0;
	int sum = 0;

	for (i = 0; i < N; i++) {
		arr[i] = rand() % MAX;
	}

	for (i = 0; i < N; i++) {
		printf("arr[%2d]:%5d\n", i, arr[i]);
		min = arr[i] < min ? arr[i] : min;
		max = arr[i] > max ? arr[i] : max;
		sum += arr[i];
	}

	printf("Min: %d\n", min);
	printf("Max: %d\n", max);
	printf("Avg: %.2f\n", sum / (float) N);

	// 选择排序(从小到大)：数组中元素分为有序序列和无序序列
	// 每一趟无序序列减少一个元素，有序序列增加一个元素
#if 0
	for (i = 0; i < N - 1; i++) {
		pos = i;

		for (j = i + 1; j < N; j++) {
			if (arr[pos] > arr[j])
				pos = j; // 选择无序序列中最小元素的下标
		}

		if (pos != i) { // 无序序列中的最小元素不是无序序列中第一个元素
			t = arr[i];
			arr[i] = arr[pos];
			arr[pos] = t;
		}
	}
#endif

	// 冒泡排序(从大到小)：每一趟确定至少一个元素的位置冒到数组最后
#if 0
	for (i = 0; i < N - 1; i++) {
		for (j = 0; j < N - i - 1; j++) {
			if (arr[j] < arr[j + 1]) { // 后一个元素小大于于前一个元素，交换
				t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
			}
		}
	}
#endif

	// 直接插入排序(从小到大)：不包含交换过程
#if 1
	for (i = 1; i < N; i++) {
		t = arr[i];

		for (j = i - 1; j >= 0; j--) {
			if (arr[j] >= t) { // 往后挪
				arr[j + 1] = arr[j];
			} else {
				// arr[j]比要插入的t小
				break;
			}
		}

		arr[j + 1] = t;
	}
#endif

	for (i = 0; i < N; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}
